package code101_200.code40_50;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 *
 */
public class _144preOrderTraversal {

    /**
     * 直接写先序遍历代码即可
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.4 MB     * , 在所有 Java 提交中击败了     * 91.47%     * 的用户
     * @param root
     * @return
     */

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp;
        stack.push(root);
        while (stack.size()!=0){
            temp = stack.pop();
            list.add(temp.val);
            if(temp.right!=null)stack.push(temp.right);
            if(temp.left!=null)stack.push(temp.left);
        }
        return list;
    }
}
